#
# @lc app=leetcode.cn id=1143 lang=python3
#
# [1143] 最长公共子序列
#

# @lc code=start
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        dp = [[0]*(len(text2)+1) for _ in text1+'0']
        for i, v1 in enumerate(text1):
            for j, v2 in enumerate(text2):
                dp[i+1][j+1] = max([dp[i][j+1], dp[i+1][j]])
                if v1==v2:
                    dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]+1)
        return dp[-1][-1]
# @lc code=end

